﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Sort
{
    class HeapSort
    {
        public static void Sort(int[] arr, int beg, int end)
        {
            InitHeap(arr);
            Sort_(arr, arr.Length);
        }

        public static void Sort_(int[] arr, int len)
        {
            if (len <= 1)
                return;

            lib.Swap<int>(arr, 0, len - 1);
            AdjustHeap(arr, 0, len - 1);
            Sort_(arr, len - 1);
        }

        static void InitHeap(int[] arr)
        {
            int maxParent = arr.Length / 2 - 1;
            for (int i = maxParent; i >= 0; i--)
            {
                AdjustHeap(arr, i, arr.Length);
            }
        }
        
        static void AdjustHeap(int[] arr, int parent, int Length)
        {
            if (parent >= Length)
                return;

            int leftChild = parent * 2 + 1;
            if (leftChild >= Length)
                return;

            int rightChild = leftChild + 1;
            if (rightChild < Length && arr[leftChild] < arr[rightChild])
            {
                if (arr[parent] < arr[rightChild])
                {
                    lib.Swap<int>(arr, parent, rightChild);
                    AdjustHeap(arr, rightChild, Length);
                }
            }
            else
            {
                int leftVal = arr[leftChild];
                if (arr[parent] < leftVal)
                {
                    lib.Swap<int>(arr, parent, leftChild);
                    AdjustHeap(arr, leftChild, Length);
                }
            }
        }

        public static void HeapAdjust(int[] array, int parent, int length)
        {
            int temp = array[parent]; 
            int child = 2 * parent + 1; 

            while (child < length)
            {
                // 如果有右孩子结点，并且右孩子结点的值大于左孩子结点，则选取右孩子结点
                if (child + 1 < length && array[child] < array[child + 1])
                {
                    child++;
                }

                if (temp >= array[child])
                    break;

                array[parent] = array[child];
                parent = child;
                child = 2 * child + 1;
            }

            array[parent] = temp;
        }

        public static void heapSort(int[] list, int k, int kk)
        {
            // 循环建立初始堆
            for (int i = list.Length / 2; i >= 0; i--) 
            {
                HeapAdjust(list, i, list.Length);
            }

            // 进行n-1次循环，完成排序
            for (int i = list.Length - 1; i > 0; i--) 
            {
                lib.Swap<int>(list, i, 0);
                HeapAdjust(list, 0, i);
            }
        }
    }
}
